

package merge_sort1;



public class Main {
    
    public static void mergesort (int[] a) {
          mergesort(a, 0, a.length-1);
          for(int j=0;j<a.length;j++)
          {
              System.out.print(a[j]+" ");
          }
          
     }

     private static void mergesort (int[] a, int l, int r) {
          //base case: a[l..r] is empty or has only one element
          if ( l>=r ) return;

          //recursion step: a[l..r] is not empty
          //divide into sublists and merge
          int m = (l+r)/2;
          mergesort (a, l, m);
          mergesort (a, m+1, r);
          merge (a, l, m, r);
     }

     //merges to sublists
     private static void merge (int[] a, int l, int m, int r) {
          //base case: second sublist is empty
          if (m+1>r) return;

          int[] b = new int[a.length];
          //create temporary array //copy a[l..m] to b[l..m]
          for (int i=l; i!=m+1; i++) {
               b[i] = a[i];
          }
          //copy a[m+1..r] to b[m+1..r] in reverse order
          for (int i=m+1; i!=r+1; i++) {
               b[i] = a[r+m+1-i];
          }
          //merge b[l..m] with b[m+1..r] to a[l..r]
          int k=l; int j=r; //pointer wandering from outside inward
          for (int i=l; i!=r+1; i++) {
               if (b[k] <= b[j]) a[i] = b[k++]; else a[i] = b[j--];
          }
     }
 public static void main(String[] args)
 {   int[] a={1,3,5,6,8,9};
     mergesort(a);
 }
    

}
